home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 27 / CU Amiga Magazine's Super CD-ROM 27 (1998)(EMAP Images)(GB)[!][issue 1998-10].iso / CUCD / Programming / Mesa / quantizers / dl1 / dl1quant.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-08-02  |  20.7 KB  |  801 lines
  1. /*
  2.  * DL1 Quantization
  3.  * ================
  4.  *
  5.  * File: dl1quant.c
  6.  * Author: Dennis Lee   E-mail: denlee@ecf.utoronto.ca
  7.  *
  8.  * Copyright (C) 1993-1997 Dennis Lee
  9.  *
  10.  * C implementation of DL1 Quantization.
  11.  * DL1 Quantization is a 2-pass color quantizer optimized for speed.
  12.  * The method was designed around the steps required by a 2-pass
  13.  * quantizer and constructing a model that would require the least
  14.  * amount of extra work.  The resulting method is extremely fast --
  15.  * about half the speed of a memcpy.  That should make DL1 Quant the
  16.  * fastest 2-pass color quantizer.
  17.  *
  18.  * This quantizer's quality is also among the best, slightly
  19.  * better than Wan et al's marginal variance based quantizer.  For
  20.  * more on DL1 Quant's performance and other related information,
  21.  * see DLQUANT.TXT included in this distribution.
  22.  *
  23.  *
  24.  * NOTES
  25.  * =====
  26.  *
  27.  * The dithering code is based on code from the IJG's jpeg library.
  28.  *
  29.  * This source code may be freely copied, modified, and redistributed,
  30.  * provided this copyright notice is attached.
  31.  * Compiled versions of this code, modified or not, are free for
  32.  * personal use.  Compiled versions used in distributed software
  33.  * is also free, but a notification must be sent to the author.
  34.  * An e-mail to denlee@ecf.utoronto.ca will do.
  35.  *
  36.  */
  37.  
  38.  
  39. /*
  40.  * dl1quant.c
  41.  *
  42.  * Modified  27 Jun 1998
  43.  * by Jarno van der Linden
  44.  * jarno@kcbbs.gen.nz
  45.  *
  46.  * Some minor additions and changes to work with AmigaMesaRTL
  47.  *
  48.  * Version 1.1  02 Aug 1998
  49.  * by Jarno van der Linden
  50.  * jarno@kcbbs.gen.nz
  51.  *
  52.  * - Changed to a quantizer plugin library
  53.  *
  54.  */
  55.  
  56.  
  57. #define DL1SRC
  58.  
  59. #include <stdlib.h>
  60. #include <string.h>
  61. #include "dl1quant.h"
  62.  
  63. #include <intuition/intuition.h>
  64. #include <proto/intuition.h>
  65. #include <proto/graphics.h>
  66. #include <proto/utility.h>
  67.  
  68. #include "gl/quantizer.h"
  69.  
  70.  
  71. /********** The following are options **********/
  72.  
  73. //#define FAST        /* improves speed but uses a lot of memory */
  74. //#define QUAL1       /* improves quality slightly (slower) */
  75. //#define QUAL2       /* improves quality slightly (slower) */
  76.  
  77. /* define *one* of the following dither options */
  78. #define DITHER1     /* 1-val error diffusion dither */
  79. //#define DITHER2     /* 2-val error diffusion dither */
  80. //#define DITHER4     /* 4-val error diffusion dither (Floyd-Steinberg) */
  81.  
  82. /********** End of options **********/
  83.  
  84. #define DITHER_MAX  20
  85.  
  86. LOCAL uchar palette[3][256];
  87. LOCAL CUBE *rgb_table[6];
  88. LOCAL ushort r_offset[256], g_offset[256], b_offset[256];
  89. LOCAL CLOSEST_INFO c_info;
  90. LOCAL int tot_colors, pal_index, did_init = 0;
  91. LOCAL ulong *squares;
  92. LOCAL FCUBE *heap = NULL;
  93. LOCAL short *dl_image = NULL;
  94.  
  95. LOCAL int bufwidth,bufheight;
  96.  
  97. struct dl1Context {
  98.     struct Window *window;
  99.     int mode;
  100.     struct DrawInfo *di;
  101.     struct BitMap bm;
  102.     struct RastPort rp;
  103.     UBYTE *qbuffer;
  104.     ULONG *palette;
  105.     ULONG numc, firstc;
  106.     int rw, rh;
  107.     int ww, wh;
  108. };
  109.  
  110.  
  111. struct dl1Context context;
  112.  
  113. #define WINWIDTH(w)        ((w)->Width - (w)->BorderLeft - (w)->BorderRight)
  114. #define WINHEIGHT(w)    ((w)->Height - (w)->BorderTop - (w)->BorderBottom)
  115.  
  116. BOOL InitWritePixelA8(void)
  117. {
  118.     int depth;
  119.  
  120.     InitBitMap(&(context.bm), context.di->dri_Depth, context.rw, 1);
  121.  
  122.     for(depth=0; depth<context.di->dri_Depth; depth++)
  123.     {
  124.         context.bm.Planes[depth] = (PLANEPTR)AllocRaster(context.rw, 1);
  125.         if(!context.bm.Planes[depth])
  126.             return FALSE;
  127.     }
  128.  
  129.     context.rp = *(context.window->RPort);
  130.     context.rp.Layer = NULL;
  131.     context.rp.BitMap = &(context.bm);
  132.  
  133.     return(TRUE);
  134. }
  135.  
  136.  
  137. void DelWritePixelA8(void)
  138. {
  139.     int depth;
  140.  
  141.     for(depth=0; depth<context.di->dri_Depth; depth++)
  142.     {
  143.         if(context.bm.Planes[depth]) FreeRaster(context.bm.Planes[depth], context.rw, 1);
  144.         context.bm.Planes[depth] = NULL;
  145.     }
  146. }
  147.  
  148.  
  149. __asm __saveds int InitQuantizer(register __a0 struct Window *window, register __d0 ULONG mode, register __d1 ULONG numcolours, register __d2 ULONG firstcolour)
  150. {
  151.     int depth;
  152.  
  153.     context.window = window;
  154.     context.mode = mode;
  155.     context.di = GetScreenDrawInfo(window->WScreen);
  156.     context.qbuffer = NULL;
  157.  
  158.     for(depth=0; depth<context.di->dri_Depth; depth++)
  159.     {
  160.         context.bm.Planes[depth] = NULL;
  161.     }
  162.  
  163.     if(mode == AMRTL_RGBAMode)
  164.     {
  165.         context.numc = numcolours;
  166.         context.firstc = firstcolour;
  167.         context.palette = calloc(1+context.numc*3+1,sizeof(ULONG));
  168.     }
  169.  
  170.     dlq_init();
  171.     dlq_start();
  172.     return 1;
  173. }
  174.  
  175.  
  176. __asm __saveds void DeleteQuantizer(void)
  177. {
  178.     dlq_finish();
  179.  
  180.     DelWritePixelA8();
  181.  
  182.     if(context.palette) free(context.palette);
  183.     context.palette = NULL;
  184.  
  185.     if(context.di) FreeScreenDrawInfo(context.window->WScreen, context.di);
  186.     context.di = NULL;
  187.  
  188.     if(context.qbuffer) free(context.qbuffer);
  189.     context.qbuffer = NULL;
  190. }
  191.  
  192.  
  193. __asm __saveds int ResizeQuantizer(register __d0 int width, register __d1 int height)
  194. {
  195.     DelWritePixelA8();
  196.     if(context.qbuffer) free(context.qbuffer);
  197.     context.qbuffer = NULL;
  198.  
  199.     bufwidth = width;
  200.     bufheight = height;
  201. #ifdef FAST
  202.     if(dl_image) free(dl_image)
  203.     dl_image = malloc(sizeof(short) * width*height);
  204. #endif
  205.  
  206.     context.rw = width;
  207.     context.rh = height;
  208.  
  209.     context.ww = WINWIDTH(context.window);
  210.     context.wh = WINHEIGHT(context.window);
  211.  
  212.     if(context.mode == AMRTL_RGBAMode)
  213.         context.qbuffer = (UBYTE *)calloc(context.rw * context.rh, sizeof(UBYTE));
  214.  
  215.     InitWritePixelA8();
  216.     return 1;
  217. }
  218.  
  219.  
  220. void dl1Quantize(unsigned long *buffer, unsigned long numc, unsigned long base, unsigned char *qbuffer,unsigned long *paltable);
  221. __asm __saveds int Quantize(register __a0 APTR buffer)
  222. {
  223.     if(context.mode == AMRTL_RGBAMode)
  224.     {
  225.         dl1Quantize((ULONG *)buffer, context.numc, context.firstc, context.qbuffer, context.palette);
  226.         LoadRGB32(ViewPortAddress(context.window), context.palette);
  227.  
  228.         if((WINWIDTH(context.window) != context.ww) || (WINHEIGHT(context.window) != context.wh))
  229.             return 1;
  230.         WritePixelArray8(context.window->RPort,
  231.                          context.window->BorderLeft , context.window->BorderTop,
  232.                          context.window->BorderLeft + context.ww-1, context.window->BorderTop + context.wh-1,
  233.                          context.qbuffer, &(context.rp));
  234.     }
  235.     else if(context.mode == AMRTL_IndexMode)
  236.     {
  237.         WritePixelArray8(context.window->RPort,
  238.                          context.window->BorderLeft , context.window->BorderTop,
  239.                          context.window->BorderLeft + context.ww-1, context.window->BorderTop + context.wh-1,
  240.                          buffer, &(context.rp));
  241.     }
  242.     return 1;
  243. }
  244.  
  245.  
  246. void dl1Quantize(unsigned long *buffer, unsigned long numc, unsigned long base, unsigned char *qbuffer,unsigned long *paltable)
  247. {
  248.     unsigned long *pp;
  249.     unsigned char *pr,*pg,*pb;
  250.     int t;
  251.  
  252.     reset();
  253.     build_table(buffer, (ulong)bufwidth * (ulong)bufheight);
  254.     reduce_table(numc);
  255.     set_palette(0, 0);
  256.     quantize_image(buffer, qbuffer, bufwidth, bufheight, 1, base);
  257.  
  258.     pp = paltable;
  259.     pr = palette[0];
  260.     pg = palette[1];
  261.     pb = palette[2];
  262.  
  263.     *pp++ = (numc<<16)+base;
  264.  
  265.     for(t=0; t<numc; t++)
  266.     {
  267.         *pp++ = ((unsigned long)(*pr++)) * 0x01010101;
  268.         *pp++ = ((unsigned long)(*pg++)) * 0x01010101;
  269.         *pp++ = ((unsigned long)(*pb++)) * 0x01010101;
  270.     }
  271.     *pp = 0;
  272. }
  273.  
  274.  
  275. #if 0
  276. /* returns 1 on success, 0 on failure */
  277. GLOBAL int
  278. dl1quant(uchar *inbuf, uchar *outbuf, int width, int height, int quant_to,
  279.      int dither, uchar userpal[3][256]) {
  280.  
  281.     if (!did_init) {
  282.     did_init = 1;
  283.     dlq_init();
  284.     }
  285.     if (dlq_start() == 0) {
  286.     dlq_finish();
  287.     return 0;
  288.     }
  289.     if (build_table(inbuf, (ulong)width * (ulong)height) == 0) {
  290.     dlq_finish();
  291.     return 0;
  292.     }
  293.     reduce_table(quant_to);
  294.     set_palette(0, 0);
  295.     if (quantize_image(inbuf, outbuf, width, height, dither) == 0) {
  296.     dlq_finish();
  297.     return 0;
  298.     }
  299.     dlq_finish();
  300.     copy_pal(userpal);
  301.  
  302.     return 1;
  303. }
  304. #endif
  305.  
  306. LOCAL void
  307. copy_pal(uchar userpal[3][256]) {
  308.     int i;
  309.  
  310.     for (i = 0; i < 256; i++) {
  311.     userpal[0][i] = palette[0][i];
  312.     userpal[1][i] = palette[1][i];
  313.     userpal[2][i] = palette[2][i];
  314.     }
  315. }
  316.  
  317. LOCAL void
  318. dlq_init(void) {
  319.     int i;
  320.  
  321.     for (i = 0; i < 256; i++) {
  322.     r_offset[i] = (i & 128) << 7 | (i & 64) << 5 | (i & 32) << 3 |
  323.               (i & 16)  << 1 | (i & 8)  >> 1;
  324.     g_offset[i] = (i & 128) << 6 | (i & 64) << 4 | (i & 32) << 2 |
  325.               (i & 16)  << 0 | (i & 8)  >> 2;
  326.     b_offset[i] = (i & 128) << 5 | (i & 64) << 3 | (i & 32) << 1 |
  327.               (i & 16)  >> 1 | (i & 8)  >> 3;
  328.     }
  329.  
  330.     for (i = (-255); i <= 255; i++)
  331.     c_info.squares[i+255] = i*i;
  332.     squares = c_info.squares + 255;
  333. }
  334.  
  335. /* returns 1 on success, 0 on failure */
  336. LOCAL int
  337. dlq_start(void) {
  338.     int i;
  339.  
  340.     rgb_table[0] = (CUBE *) calloc(sizeof(CUBE), 1);
  341.     rgb_table[1] = (CUBE *) calloc(sizeof(CUBE), 8);
  342.     rgb_table[2] = (CUBE *) calloc(sizeof(CUBE), 64);
  343.     rgb_table[3] = (CUBE *) calloc(sizeof(CUBE), 512);
  344.     rgb_table[4] = (CUBE *) calloc(sizeof(CUBE), 4096);
  345.     rgb_table[5] = (CUBE *) calloc(sizeof(CUBE), 32768);
  346.  
  347.     for (i = 0; i <= 5; i++)
  348.     if (rgb_table[i] == NULL)
  349.         return 0;
  350.  
  351.     pal_index = 0;
  352.  
  353.     heap = (FCUBE *) malloc(sizeof(FCUBE) * 32769);
  354.     if(heap == NULL)
  355.         return 0;
  356.  
  357.     return 1;
  358. }
  359.  
  360.  
  361. LOCAL void
  362. reset(void) {
  363.     memset(rgb_table[0], 0, 1*sizeof(CUBE));
  364.     memset(rgb_table[1], 0, 8*sizeof(CUBE));
  365.     memset(rgb_table[2], 0, 64*sizeof(CUBE));
  366.     memset(rgb_table[3], 0, 512*sizeof(CUBE));
  367.     memset(rgb_table[4], 0, 4096*sizeof(CUBE));
  368.     memset(rgb_table[5], 0, 32768*sizeof(CUBE));
  369.  
  370.     pal_index = 0;
  371. }
  372.  
  373.  
  374.  
  375. LOCAL void
  376. dlq_finish(void) {
  377.     if (rgb_table[0] != NULL)
  378.     free(rgb_table[0]);
  379.     if (rgb_table[1] != NULL)
  380.     free(rgb_table[1]);
  381.     if (rgb_table[2] != NULL)
  382.     free(rgb_table[2]);
  383.     if (rgb_table[3] != NULL)
  384.     free(rgb_table[3]);
  385.     if (rgb_table[4] != NULL)
  386.     free(rgb_table[4]);
  387.     if (rgb_table[5] != NULL)
  388.     free(rgb_table[5]);
  389.     if (heap != NULL)
  390.     free(heap);
  391.     if (dl_image != NULL)
  392.     free(dl_image);
  393. }
  394.  
  395. /* returns 1 on success, 0 on failure */
  396. LOCAL int
  397. build_table(uchar *image, ulong pixels) {
  398.     ulong i, index, cur_count, head, tail;
  399.     slong j;
  400.  
  401.     for (i = 0; i < pixels; i++) {
  402. #ifdef FAST
  403.     dl_image[i] = index = r_offset[image[0]] + g_offset[image[1]] + b_offset[image[2]];
  404. #else
  405.     index = r_offset[image[0]] + g_offset[image[1]] + b_offset[image[2]];
  406. #endif
  407. #ifdef QUAL1
  408.     rgb_table[5][index].r += image[0];
  409.     rgb_table[5][index].g += image[1];
  410.     rgb_table[5][index].b += image[2];
  411. #endif
  412.     rgb_table[5][index].pixel_count++;
  413.     image += 4;
  414.     }
  415.  
  416.     tot_colors = 0;
  417.     for (i = 0; i < 32768; i++) {
  418.     cur_count = rgb_table[5][i].pixel_count;
  419.     if (cur_count) {
  420.         heap[++tot_colors].level = 5;
  421.         heap[tot_colors].index = i;
  422.         rgb_table[5][i].pixels_in_cube = cur_count;
  423. #ifndef QUAL1
  424.         rgb_table[5][i].r = cur_count * (((i & 0x4000) >> 7 |
  425.                 (i & 0x0800) >> 5 | (i & 0x0100) >> 3 |
  426.                 (i & 0x0020) >> 1 | (i & 0x0004) << 1) + 4);
  427.         rgb_table[5][i].g = cur_count * (((i & 0x2000) >> 6 |
  428.                 (i & 0x0400) >> 4 | (i & 0x0080) >> 2 |
  429.                 (i & 0x0010) >> 0 | (i & 0x0002) << 2) + 4);
  430.         rgb_table[5][i].b = cur_count * (((i & 0x1000) >> 5 |
  431.                 (i & 0x0200) >> 3 | (i & 0x0040) >> 1 |
  432.                 (i & 0x0008) << 1 | (i & 0x0001) << 3) + 4);
  433. #endif
  434.         head = i;
  435.         for (j = 4; j >= 0; j--) {
  436.         tail = head & 0x7;
  437.         head >>= 3;
  438.         rgb_table[j][head].pixels_in_cube += cur_count;
  439.         rgb_table[j][head].children |= 1 << tail;
  440.         }
  441.     }
  442.     }
  443.  
  444.     for (i = tot_colors; i > 0; i--)
  445.     fixheap(i);
  446.  
  447.     return 1;
  448. }
  449.  
  450. LOCAL void
  451. fixheap(ulong id) {
  452.     uchar thres_level = heap[id].level;
  453.     ulong thres_index = heap[id].index, index, half_totc = tot_colors >> 1,
  454.       thres_val = rgb_table[thres_level][thres_index].pixels_in_cube;
  455.  
  456.     while (id <= half_totc) {
  457.     index = id << 1;
  458.  
  459.     if (index < tot_colors)
  460.         if (rgb_table[heap[index].level][heap[index].index].pixels_in_cube
  461.           > rgb_table[heap[index+1].level][heap[index+1].index].pixels_in_cube)
  462.         index++;
  463.  
  464.     if (thres_val <= rgb_table[heap[index].level][heap[index].index].pixels_in_cube)
  465.         break;
  466.     else {
  467.         heap[id] = heap[index];
  468.         id = index;
  469.     }
  470.     }
  471.     heap[id].level = thres_level;
  472.     heap[id].index = thres_index;
  473. }
  474.  
  475. LOCAL void
  476. reduce_table(int num_colors) {
  477.     while (tot_colors > num_colors) {
  478.  
  479.     uchar tmp_level = heap[1].level, t_level = tmp_level - 1;
  480.     ulong tmp_index = heap[1].index, t_index = tmp_index >> 3;
  481.  
  482.     if (rgb_table[t_level][t_index].pixel_count)
  483.         heap[1] = heap[tot_colors--];
  484.     else {
  485.         heap[1].level = t_level;
  486.         heap[1].index = t_index;
  487.     }
  488.     rgb_table[t_level][t_index].pixel_count += rgb_table[tmp_level][tmp_index].pixel_count;
  489.     rgb_table[t_level][t_index].r += rgb_table[tmp_level][tmp_index].r;
  490.     rgb_table[t_level][t_index].g += rgb_table[tmp_level][tmp_index].g;
  491.     rgb_table[t_level][t_index].b += rgb_table[tmp_level][tmp_index].b;
  492.     rgb_table[t_level][t_index].children &= ~(1 << (tmp_index & 0x7));
  493.     fixheap(1);
  494.     }
  495. }
  496.  
  497. LOCAL void
  498. set_palette(int index, int level) {
  499.     int i;
  500.  
  501.     if (rgb_table[level][index].children)
  502.     for (i = 7; i >= 0; i--)
  503.         if (rgb_table[level][index].children & (1 << i))
  504.         set_palette((index << 3) + i, level + 1);
  505.  
  506.     if (rgb_table[level][index].pixel_count) {
  507.     ulong r_sum, g_sum, b_sum, sum;
  508.  
  509.     rgb_table[level][index].palette_index = pal_index;
  510.     r_sum = rgb_table[level][index].r;
  511.     g_sum = rgb_table[level][index].g;
  512.     b_sum = rgb_table[level][index].b;
  513.     sum = rgb_table[level][index].pixel_count;
  514.     palette[0][pal_index] = (r_sum + (sum >> 1)) / sum;
  515.     palette[1][pal_index] = (g_sum + (sum >> 1)) / sum;
  516.     palette[2][pal_index] = (b_sum + (sum >> 1)) / sum;
  517.     pal_index++;
  518.     }
  519. }
  520.  
  521. LOCAL void
  522. closest_color(int index, int level) {
  523.     int i;
  524.  
  525.     if (rgb_table[level][index].children)
  526.     for (i = 7; i >= 0; i--)
  527.         if (rgb_table[level][index].children & (1 << i))
  528.         closest_color((index << 3) + i, level + 1);
  529.  
  530.     if (rgb_table[level][index].pixel_count) {
  531.     slong dist, r_dist, g_dist, b_dist;
  532.     uchar pal_num = rgb_table[level][index].palette_index;
  533.  
  534.     /* Determine if this color is "closest". */
  535.     r_dist = palette[0][pal_num] - c_info.red;
  536.     g_dist = palette[1][pal_num] - c_info.green;
  537.     b_dist = palette[2][pal_num] - c_info.blue;
  538.     dist = squares[r_dist] + squares[g_dist] + squares[b_dist];
  539.     if (dist < c_info.distance) {
  540.         c_info.distance = dist;
  541.         c_info.palette_index = pal_num;
  542.     }
  543.     }
  544. }
  545.  
  546. /* returns 1 on success, 0 on failure */
  547. LOCAL int
  548. quantize_image(uchar *in, uchar *out, int width, int height, int dither, int base) {
  549.     if (!dither) {
  550.     ulong i, pixels = width * height;
  551.     ushort level, index;
  552.     uchar tmp_r, tmp_g, tmp_b, cube, *lookup;
  553.  
  554.     lookup = malloc(sizeof(char) * 32768);
  555.     if (lookup == NULL)
  556.         return 0;
  557.  
  558.     for (i = 0; i < 32768; i++)
  559.         if (rgb_table[5][i].pixel_count) {
  560.         tmp_r = (i & 0x4000) >> 7 | (i & 0x0800) >> 5 |
  561.             (i & 0x0100) >> 3 | (i & 0x0020) >> 1 |
  562.             (i & 0x0004) << 1;
  563.         tmp_g = (i & 0x2000) >> 6 | (i & 0x0400) >> 4 |
  564.             (i & 0x0080) >> 2 | (i & 0x0010) >> 0 |
  565.             (i & 0x0002) << 2;
  566.         tmp_b = (i & 0x1000) >> 5 | (i & 0x0200) >> 3 |
  567.             (i & 0x0040) >> 1 | (i & 0x0008) << 1 |
  568.             (i & 0x0001) << 3;
  569. #ifdef QUAL2
  570.         lookup[i] = bestcolor(tmp_r, tmp_g, tmp_b);
  571. #else
  572.         c_info.red   = tmp_r + 4;
  573.         c_info.green = tmp_g + 4;
  574.         c_info.blue  = tmp_b + 4;
  575.         level = 0;
  576.         index = 0;
  577.         for (;;) {
  578.             cube = (tmp_r&128) >> 5 | (tmp_g&128) >> 6 | (tmp_b&128) >> 7;
  579.             if ((rgb_table[level][index].children & (1 << cube)) == 0) {
  580.             c_info.distance = ~0L;
  581.             closest_color(index, level);
  582.             lookup[i] = c_info.palette_index;
  583.             break;
  584.             }
  585.             level++;
  586.             index = (index << 3) + cube;
  587.             tmp_r <<= 1;
  588.             tmp_g <<= 1;
  589.             tmp_b <<= 1;
  590.         }
  591. #endif
  592.         }
  593.  
  594.     for (i = 0; i < pixels; i++) {
  595. #ifdef FAST
  596.         out[i] = lookup[dl_image[i]]+base;
  597. #else
  598.         out[i] = lookup[r_offset[in[0]] + g_offset[in[1]] + b_offset[in[2]]]+base;
  599.         in += 4;
  600. #endif
  601.     }
  602.  
  603.     free(lookup);
  604.     } else {
  605. #if defined(DITHER2) || defined(DITHER4)
  606.     slong i, j, r_pix, g_pix, b_pix, offset, dir, two_val,
  607.           odd_scanline = 0, err_len = (width + 2) * 3;
  608.     uchar *range_tbl = malloc(3 * 256), *range = range_tbl + 256;
  609.     sshort *lookup  = malloc(sizeof(short) * 32768),
  610.            *erowerr = malloc(sizeof(short) * err_len),
  611.            *orowerr = malloc(sizeof(short) * err_len),
  612.            *thisrowerr, *nextrowerr;
  613.     schar *dith_max_tbl = malloc(512), *dith_max = dith_max_tbl + 256;
  614.  
  615.  
  616.  
  617.  
  618.     if (range_tbl == NULL || lookup == NULL ||
  619.         erowerr == NULL || orowerr == NULL || dith_max_tbl == NULL) {
  620.         if (range_tbl != NULL)
  621.         free(range_tbl);
  622.         if (lookup != NULL)
  623.         free(lookup);
  624.         if (erowerr != NULL)
  625.         free(erowerr);
  626.         if (orowerr != NULL)
  627.         free(orowerr);
  628.         if (dith_max_tbl != NULL)
  629.         free(dith_max_tbl);
  630.         return 0;
  631.     }
  632.  
  633.     for (i = 0; i < err_len; i++)
  634.         erowerr[i] = 0;
  635.  
  636.     for (i = 0; i < 32768; i++)
  637.         lookup[i] = -1;
  638.  
  639.     for (i = 0; i < 256; i++) {
  640.         range_tbl[i] = 0;
  641.         range_tbl[i + 256] = (uchar) i;
  642.         range_tbl[i + 512] = 255;
  643.     }
  644.  
  645.     for (i = 0; i < 256; i++) {
  646.         dith_max_tbl[i] = -DITHER_MAX;
  647.         dith_max_tbl[i + 256] = DITHER_MAX;
  648.     }
  649.     for (i = -DITHER_MAX; i <= DITHER_MAX; i++)
  650.         dith_max_tbl[i + 256] = i;
  651.  
  652.     for (i = 0 ; i < height; i++) {
  653.         if (odd_scanline) {
  654.         dir = -1;
  655.         in  += (width - 1) * 4;
  656.         out += (width - 1);
  657.         thisrowerr = orowerr + 3;
  658.         nextrowerr = erowerr + width * 3;
  659.         } else {
  660.         dir = 1;
  661.         thisrowerr = erowerr + 3;
  662.         nextrowerr = orowerr + width * 3;
  663.         }
  664.         nextrowerr[0] = nextrowerr[1] = nextrowerr[2] = 0;
  665.         for (j = 0; j < width; j++) {
  666. #ifdef DITHER2
  667.         r_pix = range[(thisrowerr[0] >> 1) + in[0]];
  668.         g_pix = range[(thisrowerr[1] >> 1) + in[1]];
  669.         b_pix = range[(thisrowerr[2] >> 1) + in[2]];
  670. #else
  671.         r_pix = range[((thisrowerr[0] + 8) >> 4) + in[0]];
  672.         g_pix = range[((thisrowerr[1] + 8) >> 4) + in[1]];
  673.         b_pix = range[((thisrowerr[2] + 8) >> 4) + in[2]];
  674. #endif
  675.         offset = (r_pix&248) << 7 | (g_pix&248) << 2 | b_pix >> 3;
  676.         if (lookup[offset] < 0)
  677.             lookup[offset] = bestcolor(r_pix, g_pix, b_pix);
  678.         *out = lookup[offset]+base;
  679.         r_pix = dith_max[r_pix - palette[0][lookup[offset]]];
  680.         g_pix = dith_max[g_pix - palette[1][lookup[offset]]];
  681.         b_pix = dith_max[b_pix - palette[2][lookup[offset]]];
  682. #ifdef DITHER2
  683.         nextrowerr[0  ]  = r_pix;
  684.         thisrowerr[0+3] += r_pix;
  685.         nextrowerr[1  ]  = g_pix;
  686.         thisrowerr[1+3] += g_pix;
  687.         nextrowerr[2  ]  = b_pix;
  688.         thisrowerr[2+3] += b_pix;
  689. #else
  690.         two_val = r_pix * 2;
  691.         nextrowerr[0-3]  = r_pix;
  692.         r_pix += two_val;
  693.         nextrowerr[0+3] += r_pix;
  694.         r_pix += two_val;
  695.         nextrowerr[0  ] += r_pix;
  696.         r_pix += two_val;
  697.         thisrowerr[0+3] += r_pix;
  698.         two_val = g_pix * 2;
  699.         nextrowerr[1-3]  = g_pix;
  700.         g_pix += two_val;
  701.         nextrowerr[1+3] += g_pix;
  702.         g_pix += two_val;
  703.         nextrowerr[1  ] += g_pix;
  704.         g_pix += two_val;
  705.         thisrowerr[1+3] += g_pix;
  706.         two_val = b_pix * 2;
  707.         nextrowerr[2-3]  = b_pix;
  708.         b_pix += two_val;
  709.         nextrowerr[2+3] += b_pix;
  710.         b_pix += two_val;
  711.         nextrowerr[2  ] += b_pix;
  712.         b_pix += two_val;
  713.         thisrowerr[2+3] += b_pix;
  714. #endif
  715.         thisrowerr += 3;
  716.         nextrowerr -= 3;
  717.         in  += dir * 4;
  718.         out += dir;
  719.         }
  720.         if ((i % 2) == 1) {
  721.         in  += (width + 1) * 4;
  722.         out += (width + 1);
  723.         }
  724.         odd_scanline = !odd_scanline;
  725.     }
  726.  
  727.     free(range_tbl);
  728.     free(lookup);
  729.     free(erowerr);
  730.     free(orowerr);
  731.     free(dith_max_tbl);
  732. #else
  733.     slong i, j, r_pix, g_pix, b_pix, r_err, g_err, b_err, offset;
  734.     uchar *range_tbl = malloc(3 * 256), *range = range_tbl + 256;
  735.     sshort *lookup = malloc(sizeof(short) * 32768);
  736.  
  737.     if (range_tbl == NULL || lookup == NULL) {
  738.         if (range_tbl != NULL)
  739.         free(range_tbl);
  740.         if (lookup != NULL)
  741.         free(lookup);
  742.         return 0;
  743.     }
  744.  
  745.     for (i = 0; i < 32768; i++)
  746.         lookup[i] = -1;
  747.  
  748.     for (i = 0; i < 256; i++) {
  749.         range_tbl[i] = 0;
  750.         range_tbl[i + 256] = (uchar) i;
  751.         range_tbl[i + 512] = 255;
  752.     }
  753.  
  754.     for (i = 0; i < height; i++) {
  755.         r_err = g_err = b_err = 0;
  756.         for (j = width - 1; j >= 0; j--) {
  757.         r_pix = range[(r_err >> 1) + in[0]];
  758.         g_pix = range[(g_err >> 1) + in[1]];
  759.         b_pix = range[(b_err >> 1) + in[2]];
  760.         offset = (r_pix&248) << 7 | (g_pix&248) << 2 | b_pix >> 3;
  761.         if (lookup[offset] < 0)
  762.             lookup[offset] = bestcolor(r_pix, g_pix, b_pix);
  763.         *out++ = lookup[offset]+base;
  764.         r_err = r_pix - palette[0][lookup[offset]];
  765.         g_err = g_pix - palette[1][lookup[offset]];
  766.         b_err = b_pix - palette[2][lookup[offset]];
  767.         in += 4;
  768.         }
  769.     }
  770.  
  771.  
  772.  
  773.     free(range_tbl);
  774.     free(lookup);
  775. #endif
  776.     }
  777.     return 1;
  778. }
  779.  
  780. LOCAL int
  781. bestcolor(int r, int g, int b) {
  782.     ulong i, bestcolor, curdist, mindist;
  783.     slong rdist, gdist, bdist;
  784.  
  785.     r = (r & 248) + 4;
  786.     g = (g & 248) + 4;
  787.     b = (b & 248) + 4;
  788.     mindist = 200000;
  789.     for (i = 0; i < tot_colors; i++) {
  790.     rdist = palette[0][i] - r;
  791.     gdist = palette[1][i] - g;
  792.     bdist = palette[2][i] - b;
  793.     curdist = squares[rdist] + squares[gdist] + squares[bdist];
  794.     if (curdist < mindist) {
  795.         mindist = curdist;
  796.         bestcolor = i;
  797.     }
  798.     }
  799.     return (int)bestcolor;
  800. }
  801.